package leetcode_1_200;

import com.sun.xml.internal.ws.message.ByteArrayAttachment;

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.Deque;
import java.util.PriorityQueue;

public class LeeCode_84 {
    public static void main(String[] args) {
//        System.out.println(largestRectangleArea(new int[]{5, 5, 1, 7, 1, 1, 5, 2, 7, 6}));
        System.out.println(largestRectangleArea(new int[]{2,5,5,3,1}));
    }
    private static int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] tmp = new int[n + 2];
        System.arraycopy(heights, 0, tmp, 1, n);
        int ans= 0;
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < tmp.length; i++) {
            while (!deque.isEmpty() && tmp[deque.peek()] > tmp[i]){
                int h = tmp[deque.pop()];
                ans = Math.max(ans, h * (i - deque.peek() - 1));
            }
            deque.push(i);
        }
        return ans;
    }
}